package Hot_100;
/*分析：
*   回文：一个串,从左边读和从右边读取是一样的
* */
public class T5_longestPalindrome {
    public static void main(String[] args) {
        T5_longestPalindrome t5_longestPalindrome = new T5_longestPalindrome();
        String s = t5_longestPalindrome.longestPalindrome_test1("babad");
        System.out.println(s);
    }

    public String longestPalindrome_test4(String s) {
        int len=s.length();
        int begin=0,len_max=0;
        if (len < 2) {
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i]=true;
        }

        char[] charArray = s.toCharArray();
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < len; i++) {
                if(charArray[i]!=charArray[j]){
                    dp[i][j]=false;
                }else{
                    if((j-1)-(i+1)+1<2){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }

                int s_len = j - i + 1;
                if (s_len > len_max &&dp[i][j]) {
                    len_max=s_len;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+len_max);
    }

    //  ----------------------------------------------------------------------
    //    方法3 动态规划 时间复杂度为O(n^2)
/*         动态规划是由小问题到大问题的过程
           难点是要知道怎么知道要用dp来解决这个问题；怎么知道状态转移方程；
           然后是填表，矩阵表示的意思
* */
    public String longestPalindrome_test3(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;

//        dp[i][j]表示s[i..j]是否为回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) { //初始化对角线
            dp[i][i]=true;
        }

        char[] charsArray = s.toCharArray();
//        左下角先填 按列填
        for (int j = 1; j < len; j++) {     //列 从第1列开始
            for (int i = 0; i < j; i++) {   //行 从第0行开始
                if (charsArray[i] != charsArray[j]) { //两个字符不相等可直接判断
                    dp[i][j]=false;
                }else {
                    if (j - i < 3) {    // 是由j-1-(i+1)+1<2化简来的，即如果i,j之间的长度小于等于1(i,j之间最多只有一个字符)，那么肯定满足回文串
                        dp[i][j]=true;
                    }else{              //如果i,j之间存在两个及以上的字符，那么就需要参考左下角的(此时的情况是charsArray[i]==charsArray[j])
//                        如果左下角为true，则对应的也应该为true
                        dp[i][j]=dp[i+1][j-1];
                    }
                }

//                只要dp[i][j]==true成立，就表示子串s[i...j]是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }



//    -----------------------------------------------------------------------------------------------
    //方法2   中心扩展算法 时间复杂度为O(n^2)
    public String longestPalindrome_test2(String s) {
        int len=s.length();
        if (len < 2) {
            return s;
        }
        int maxLen=1;
        int begin=0;

        char[]charArray=s.toCharArray();

        for (int i = 0; i < len; i++) {                                  //从字符串的第一个字符开始遍历，每次以当前字符为中心往两边扩展，判断是否回文
            int oddLen = expandAroundCenter(charArray, i, i);            //以当前字符为中心扩展(按奇数个向两边扩展)
            int evenLen = expandAroundCenter(charArray, i, i + 1);  //以当前字符及其右边的字符作为中心 去扩展(按偶数个向两边扩展)
            int curMaxLen = Math.max(oddLen, evenLen);                   //取最大长度
            if (curMaxLen > maxLen) {
                maxLen=curMaxLen;
                begin=i-(maxLen-1)/2; //画图可发现规律
            }
        }
        return s.substring(begin, begin + maxLen);
    }
//    以某个位置进行扩展，求出得到的回文字符的长度
    int expandAroundCenter(char[] charArray, int left, int right) {
        int len=charArray.length;
        int i=left;
        int j=right;
        while (i>=0&&j<len){
            if (charArray[i] == charArray[j]) { //向两边扩散
                i--;
                j++;
            }else {
                break;
            }
        }
        return j-i-1;   //返回回文子串的长度  (i-j+1)-2   减2是因为条件不符合的时候i,j都指向子串外边了，所以要-2才是长度
    }



//  ------------------------------------------------------
//    方法1 暴力法   (对每一个子串进行回文检查)  时间复杂度 O(n^3)
//    力扣超时了
    String longestPalindrome_test1(String s) {
        int len = s.length(), max_len = 1,start=0,end=0;

        if (len < 2) { //只有一个字符的情况
            return s;
        }

        for (int i = 0; i < len - 1; i++) {
            for (int j = i+1; j < len; j++) {
                if (checkPalindrome(s, i, j) && max_len < j - i + 1) {
                    max_len=j-i+1;
                    start=i;
                    end=j;
                }
            }
        }
        return s.substring(start, end+1);     //注意substring是左闭右开
    }

//    判断是否回文
     boolean checkPalindrome(String str,int begin,int end) {
         while (begin < end) {
             if (str.charAt(begin) != str.charAt(end)) {
                 return false;
             }
             begin++;
             end--;
         }
         return true;
    }
}